Technical Field of the Invention
This invention most generally relates to the process of rendering a synthetic image with a computer. More particularly, the present invention relates to an apparatus and process of ray tracing.
Background of the Invention
Ray Tracing
Ray tracing is one of several methods of rendering an image from a computer scene description. It is distinguished from other methods by the high quality of the resulting images, which can include shadows, reflections, and refractive effects.
FIG. 1 illustrates the basic concept behind ray tracing. In computer rendering, a bitmap of pixels 3 can be thought of as suspended a short distance in front of an eye point 1. The task of the renderer is to find the color value for each bitmap pixel that represents the light seen from the eye point coming from the scene in the direction of that pixel.
The ray tracing method accomplishes this for each pixel by tracing a ray from the eye point through that pixel into the scene, then determining the qualities of the light emanating from the scene backwards along the ray towards the eye point. Ray 2 in FIG. 1 is an example of this. Ray 2 is traced in the view direction corresponding to the center of the fourth pixel from the right in the third row down. The ray tracer performs some computations to eventually determine that the first scene object ray 2 intersects is sphere 4. The ray tracer then computes the light color and intensity reflected by the sphere backwards along the ray from the intersection point. This light color and intensity then becomes one data point of a known color value within the bitmap, in this case at the center of the fourth pixel from the right in the third row down.
The fundamental operation in a ray tracer is to find the apparent color and intensity of the light coming back along a ray. This is known as xe2x80x9ctracingxe2x80x9d the ray.
Ray Recursion
Note that this operation of tracing a ray does not require that the ray start at the eye point, or any other point. The name xe2x80x9ceye rayxe2x80x9d is commonly used to distinguish rays that originate at the eye point from those that originate elsewhere. The ability to find the light coming to any specific point from any specific direction is used inside the ray tracer to produce effects like shadows, refraction, and transparent objects.
FIG. 2 illustrates how a ray tracer might create and trace additional rays as part of the overall effort of tracing a single eye ray. As in FIG. 1, ray 2 is traced from the eye point 1. The first scene object intersected by ray 2 is the transparent object 5. The light seen from a point on a transparent object comes from two possible directions, the light reflected off the surface and the light transmitted through the object. The ray tracer creates and traces ray 6 to determine that portion of ray 2 resulting from the transmitted light, and ray 9 to determine the reflected portion. The result for ray 2 then becomes a weighted sum of the results for rays 6 and 9.
This process continues deeper. The value of ray 6 is a combination of the internal reflection, solved by tracing ray 8, and the transmitted light entering object 5, solved by ray 7. Ray 7 in turn strikes the reflective object 10, which requires tracing ray 11 in the direction the reflected light comes from. Meanwhile ray 9 intersects the opaque object 12. The light perceived backwards along ray 9 depends on the illumination at the point where ray 9 intersects object 12. Ray 13 is traced in a slightly different manner to determine whether the light 14 shines on the point on object 12 or whether the light is occluded by another object. In this case no object occludes the light, and light 14 is therefore taken into account in determining the perceived light back along ray 9. If the light had been occluded, then it would not have been taken into account. This would have yielded the visual effect of the point on object 12 being in a shadow from light source 14.
Note that ray 13 is traced in a different manner. The ray tracer does not solve for the light coming back along the ray, but rather whether the ray makes it to the light source or not. This type of ray is commonly referred to as a xe2x80x9clight rayxe2x80x9d.
Recursively launching additional rays as part of solving a previous ray is how ray tracers simulate many of the effects they are well known for. In FIG. 2, rays 9 and 11 provide the effect of reflective objects. Rays 6 and 7 provide transparency, ray 8 internal reflections, and launching light rays such as ray 13 provides for shadows.
Finding Ray/Object Intersections
Part of a ray tracer""s job in tracing a ray is to determine which scene object, if any, is the first intersected by the ray. The simplistic approach is to check the ray against every object in the scene. While this works, it requires far too much computation to be a useful method. All xe2x80x9creal worldxe2x80x9d ray tracers employ some sort of speedup technique aimed at eliminating unnecessary ray/object intersection checks.
There are two broad classes of techniques for reducing the number of ray/object intersection checks to perform. These are called xe2x80x9cobject hierarchyxe2x80x9d and xe2x80x9cspace subdivisionxe2x80x9d. The object hierarchy techniques group a set of objects together and find a simple bounding volume that encloses the whole group, like a sphere or a box. Rays are then intersected with the bounding volume. If the ray does not intersect the bounding volume then there is no need to check for intersection with the objects inside the bounding volume, since none of these objects could possibly intersect the ray.
The bounding volumes can also be arranged in a hierarchy. Thus, a bounding volume may contain scene objects and other bounding volumes. A scene may then consist of only a small number of bounding volumes at the top level. Intersection checks are only performed on the objects within a bounding volume if the ray is found to intersect that bounding volume.
Object hierarchy techniques vary from each other by how the objects within a bounding volume are chosen, the shape of the bounding volumes, how the bounding volumes are found, etc.
The space subdivision techniques subdivide the scene volume instead of the list of objects. The scene space is subdivided into chunks. The data for each chunk contains a list of all the scene objects that could result in a positive ray/object intersection check within the chunk. As a ray is traced, the chunk database is traversed in order along the ray. The ray is checked for intersection with all the objects in each chunk before proceeding to the next chunk along the ray. Only a small number of ray/object intersection checks are performed if the chunk only contains a small number of objects.
Space subdivision techniques can also be static or dynamic. In a static system, all the chunks are found and their object lists determined before any rays are traced. A dynamic system allows chunks to be created, deleted, and otherwise rearranged dynamically, driven by rays being traced through the scene. Static systems may require less overall computation to generate the chunks and their lists of objects since this is all done once up front. The chunks in static systems may also be more regular, thereby decreasing the computation required in determining the next chunk along a ray.
The main advantage of dynamic systems is that they only create complexity (requiring computation and memory) when and where it is needed, based on the ray activity and other criteria. For example, the space around a complex object behind a wall from the eye point may never be subdivided if no rays are traced behind the wall. Some static space subdivision techniques and generally all dynamic techniques are hierarchical. If an existing chunk is deemed too complex, it is subdivided into two or more sub-chunks. This process is repeated on the sub-chunks until they are no longer too complex to require subdivision, or some arbitrary subdivision limit has been reached.
An example of a static non-hierarchical technique is where the scene space is a parallelepiped broken into 32 by 32 by 32 chunks of equal dimensions. This requires only simple data structures and it is simple to step a ray from one chunk to the next. The disadvantage is when the objects in the scene are not uniformly distributed (which they usually aren""t). In that case, some chunks may contain a large number of objects, while other parts of the scene space contain many abutting empty chunks that the ray must step through before the next intersection check is performed.
An example of a hierarchical technique is an octree. The scene space is a parallelepiped that starts out being a single chunk. If a chunk is too complex (contains too many objects, for example), then it is divided in half along each of the major planes, yielding eight equal-sized sub-chunks. Each sub-chunk is now treated like the original chunk and subdivided if too complex. This process is repeated until all chunks are sufficiently simple or a subdivision limit has been reached. The advantage is that finer subdivision can be afforded where and when needed because subdivision is much coarser where the scene space is empty or where there has been no ray activity. Since empty chunks are not subdivided, a ray needs to step through fewer chunks where there are no objects. The drawback is that stepping from one chunk to the next is more complex, since chunks are of different sizes.
Prior Art
U.S. Pat. No. 5,583,975 discusses scene subdivision for ray tracing. However it is limited to static and non-hierarchical subdivision of the scene volume, using a power of 2 subdivision in each dimension. It does discuss other subdivision techniques, but these are limited to 2D subdivision of the image plane, not the scene volume.
Scene subdivision for ray tracing is disclosed in U.S. Pat. No. 5,594,844, but is limited to non-hierarchical schemes where the scene volume is divided by an integer number of slices in each dimension. The invention is a means for determining what those integer dividing values for each dimension should be.
U.S. Pat. No. 5,933,146 discusses some amount of ray tracing hardware. However, it is limited to tracing multiple rays together as a group with a common pass through the scene database. It also only discusses the object hierarchy (bounding volumes) speedup method, not the space subdivision method.
Current ray tracing systems are unable to provide accelerated ray tracing. What is needed is a methodology and a device for incorporating the ray tracing process in a hardware implementation that provides fast and accurate image rendering.
An object of the invention includes an apparatus that performs the hierarchical space subdivision technique of accelerating a ray tracer, which can also be done dynamically. A preferred embodiment is a fully recursive and dynamic system employing an octree hierarchy. One point of novelty is that the implementation is accomplished through hard-wired electronics instead of software. The hard-wires implementation is designed with the accompanying adjustments to better suite the hardware implementation. A further object of the invention specifically claims caching of scene object descriptions, specific subdivision criteria, and other refinements.
An object of the invention is an apparatus to represent a ray tracing scene database using a directed acyclic graph, comprising a memory means for storing directed acyclic graph structures and scene data, wherein the directed acyclic graph structures and the scene data are individual data elements. There is a logic section for computing memory addresses of the directed acyclic graph structures and the scene data wherein the logic section processes the individual data elements such that the individual data elements are presented as the directed acyclic graph and scene objects to the ray tracing system.
A further object is a means of determining a sequence of directed acyclic graph nodes corresponding to a sequence of scene sub-spaces traversed by a ray.
Another object includes a means of maintaining statistical information for each of the directed acyclic graph nodes. Additionally, wherein the statistical information is used to derive a number of rays that have been traced through each of the directed acyclic graph nodes.
Yet another object is for an apparatus wherein the statistical information is used to derive a number of the rays that have intersected the scene objects in each of the directed acyclic graph nodes.
An object of the invention is an apparatus comprising a means for determining whether to collapse the directed acyclic graph nodes based upon the statistical information. An additional object is an apparatus comprising a means for determining whether to subdivide one of the directed acyclic graph nodes based upon the statistical information.
An additional object is an apparatus comprising a hardware means for determining which of the scene objects reside in subdivided directed acyclic graph nodes.
Another object includes an apparatus comprising a caching means for temporarily storing information about the scene objects retrieved from the memory means.
Yet another object is an apparatus comprising a means for combining a plurality of the directed acyclic graph nodes into a lesser number of the directed acyclic graph nodes.
A further object is an apparatus comprising a means for subdividing a single directed acyclic graph node into a plurality of subdivided directed acyclic graph nodes.
An object of the invention is an apparatus to represent a ray tracing scene database using an octree, comprising a memory means for storing octree structures and scene data, wherein the octree structures and the scene data are individual data elements. There is a logic section for computing memory addresses of the octree structures and the scene data wherein the logic section processes the individual data elements such that the individual data elements are presented as the octree and scene objects to the ray tracing system.
A further object is an apparatus comprising a means of determining a sequence of octree nodes corresponding to a sequence of scene sub-spaces traversed by a ray.
An additional object is an apparatus comprising a means of maintaining statistical information for each of the octree nodes.
Yet a further object is an apparatus wherein the statistical information is used to derive a number of rays that have been traced through each of the octree nodes. Furthermore, the present invention includes an apparatus wherein the statistical information is used to derive a number of the rays that have intersected the scene objects in each of the octree nodes.
And, an object of the invention is an apparatus comprising a means for determining whether to collapse the octree nodes based upon the statistical information. Also, an apparatus comprising a means for determining whether to subdivide one of the octree nodes based upon the statistical information.
Another object is an apparatus comprising a hardware means for determining which of the scene objects reside in subdivided octree nodes.
And yet another object is an apparatus comprising a caching means for temporarily storing information about the scene objects retrieved from the memory means.
One further object is an apparatus comprising a means for combining a plurality of the octree nodes into a lesser number of the octree nodes.
Additionally, an object is an apparatus comprising a means for subdividing a single octree node into eight subdivided octree nodes.
An object of the invention is a method of rendering an image by ray tracing, comprising subdividing a scene into a plurality of scene subspaces, wherein a plurality of scene objects reside within the scene subspaces. Another step is for storing directed acyclic graph information describing the scene and the scene objects. A final step includes processing the directed acyclic graph information in a logic unit and outputting the image.
Still other objects and advantages of the present invention will become readily apparent to those skilled in this art from the detailed description, wherein we have shown and described only a preferred embodiment of the invention, simply by way of illustration of the best mode contemplated by us on carrying out our invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention.